package similarity.topological;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import linkprediction.Graph;
import linkprediction.Node;
import linkprediction.Ranking;
import similarity.NetworkSimilarity;

public class GraphDistance extends NetworkSimilarity {
	
	
	protected static Map<Node,Map<Node,Integer>> distanceMap = new HashMap<Node,Map<Node,Integer>>();
	
	 public final static String NAME = "GD";
	    public final static String FULL_NAME = "Graph Distance (GD)";

		
		public double graphDistance(Map<Node, Set<Node>> trainingGraph, Node x,
				Node y) {
			
			return -1.0*shortestPath(trainingGraph, x, y, new HashSet<Node>());
		}

		private int shortestPath(Map<Node, Set<Node>> graph, Node startNode, Node endNode, Set<Node> visited) {
			if(distanceMap.containsKey(startNode)){
				if( distanceMap.get(startNode).containsKey(endNode))
					return distanceMap.get(startNode).get(endNode);
				else
					return Integer.MAX_VALUE;
			}
			else if(distanceMap.containsKey(endNode)){
				if( distanceMap.get(endNode).containsKey(startNode))
					return distanceMap.get(endNode).get(startNode);
				else
					return Integer.MAX_VALUE;
			}
			
			Map<Node, Integer> dist = new HashMap<Node, Integer>();
			Map<Node, Node> previous = new HashMap<Node, Node>();
			

			Map<Node, Integer> queue = new HashMap<Node, Integer>();

			dist.put(startNode, 0);
			queue.put(startNode, 0);
			previous.put(startNode, null);
			Node u;
			int alt = 0;
			int distV;
			while (!queue.isEmpty()) {
				u = findNodeWithMinimumValue(queue);
				Integer d = queue.remove(u);

				if( !graph.containsKey(u)) continue;
				for(Node v:graph.get(u)){
				
					alt = dist.containsKey(u) ? dist.get(u) + 1 : Integer.MAX_VALUE;
					distV = dist.containsKey(v) ? dist.get(v) : Integer.MAX_VALUE;
					
					if(visited.contains(v)){
						continue;
					}	

					if (alt < distV) {
						dist.put(v, alt);
						previous.put(v, u);
						queue.put(v, alt);
					}
				}

			}
			distanceMap.put(startNode, dist);

			return dist.containsKey(endNode)? dist.get(endNode):Integer.MAX_VALUE; 
			
			

		}
		
		private Node findNodeWithMinimumValue(Map<Node, Integer> queue) {
			Iterator<Entry<Node, Integer>> iter = queue.entrySet().iterator();
			int min = Integer.MAX_VALUE;
			Node minNode = null;
			while (iter.hasNext()) {
				Map.Entry<Node, Integer> entry = iter.next();
				if (entry.getValue() < min) {
					min = entry.getValue();
					minNode = entry.getKey();
				}
			}
			return minNode;
		}

		@Override
		public String getName() {
			return NAME;
		}

		@Override
		public String getFullName() {
			return FULL_NAME;
		}

		@Override
		public double getScore(Graph aGraph, Node v1, Node v2) {
			return graphDistance(aGraph.getGraphMap(), v1, v2);
		}


		@Override
		public double getScore(Node v1, Node v2) {
			// TODO Auto-generated method stub
			return 0;
		}
}